package cn.bouncyslime.algorithms.sort.mergeSort;
/*
 * 归并排序将一个大的数组分割为小的数组，然后对小的数组进行排序，之后再将有序的小数组合并成一个大数组（排序）
 * 该程序使用递归方式实现
 * */
public class MergeSort2 {
	
	// 程序递归主体
	public void mergeSort(int[] array, int[] array2, int left, int right) {
		if(left<right) {
			int middle = (left+right)/2;	// 得到中轴，划分左右两个子数组
			mergeSort(array, array2, left, middle);	
			mergeSort(array, array2, middle+1, right);
			merge(array, array2, left, middle, right);		// 合并并排序到数组array2中
			copy(array, array2, left, right);		// 将array2中排好序的子数组复制回数组array中原有的位置
			printArrayOfRange(array, left, middle);
			printArrayOfRange(array, middle+1, right);
			System.out.println("下面为array2 ");
			printArray(array2);
			System.out.println("下面为array ");
			printArray(array);
		}
	}
	
	// 将子数组进行归并并排序，子数组在array中的范围为left--right
	public void merge(int[] array, int[] array2, int left, int middle, int right) {
		int leftIndex = left;
		int rightIndex = middle + 1;
		int tmpIndex = left;	// 用来向array2数组中放东西，tmpIndex为要放东西的索引
		while(leftIndex <= middle && rightIndex <= right) {
			if(array[leftIndex] <= array[rightIndex]) {
				array2[tmpIndex++] = array[leftIndex++];
			}else {
				array2[tmpIndex++] = array[rightIndex++];
			}
		}
		while(leftIndex <= middle) {
			array2[tmpIndex++] = array[leftIndex++];
		}
		while(rightIndex <= right) {
			array2[tmpIndex++] = array[rightIndex++];
		}
	}
	// 从array2复制到数组array
	public void copy(int[] array, int[] array2, int left, int right) {
		for(int i=left; i<=right; i++) {
			array[i] = array2[i];
		}
	}
	// 打印输出数组
	public void printArray(int[] array) {
		for(int i=0; i<array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
	// 按照所要求的范围输出数组
	public void printArrayOfRange(int[] array, int start, int end) {
		for(int i=start; i<=end; i++) {
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
//		int[] array = {49, 38, 65, 97, 76, 13, 27};
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		int[] array2 = new int[array.length];
		MergeSort2 ms = new MergeSort2();
		System.out.println("排序前：");
		ms.printArray(array);
		ms.mergeSort(array, array2, 0, array.length-1);
	}
}
